package com.mj.listen2._05_回溯;

public class Queens2 {

    // 一共有多少种合理的摆法
    int ways = 0;

    // 该变量不是必须, 仅仅是为了打印
    int[] queens;
    // 数组用于判断当前列是否已经摆放过皇后
    boolean[] cols;
    // 标记着某一对角线是否有皇后了(左上角->右下角)
    boolean[] leftTop;
    // 标记着某一对角线是否有皇后了(右上角->左下角)
    boolean[] rightTop;

    public static void main(String[] args) {
        new Queens2().placeQueens(8);
    }

    /**
     * n 皇后, 摆放所有皇后
     */
    private void placeQueens(int n) {
        if (n < 1) return;
        queens = new int[n];
        cols = new boolean[n];
        leftTop = new boolean[(n << 1) - 1];
        rightTop = new boolean[leftTop.length]; // 上面已经做过一次运算,无需再做
        place(0);// 从第0行开始摆放皇后
        System.out.println(n + "皇后一共有" + ways + "种摆法");
    }

    private void place(int row) {
        // 如果已经放到第n行,说明找到了一种n皇后的摆法
        if (row == queens.length) {
            ways++;
            show();
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            if (cols[col]) continue; // 第col列已经有皇后, 继续下一轮
            // 计算左上->右下对角线的索引
            int ltIndexl = row - col + cols.length - 1;
            if (leftTop[ltIndexl]) continue;// 第ltIndexl位置已经有皇后, 继续下一轮
            // 计算右上->右下对角线的索引
            int rtIndex = row + col;
            if (rightTop[rtIndex]) continue;// 第rtIndex位置已经有皇后, 继续下一轮
            // 记录摆放的皇后，为了方便打印
            queens[row] = col;
            // 摆放皇后
            cols[col] = leftTop[ltIndexl] = rightTop[rtIndex] = true;
            // 遍历下一行
            place(row + 1);
            // 复位，因为如果此过程方法是错的，那么回溯回来的时候，应该是"干净的"棋盘，不能受上一次影响
            cols[col] = leftTop[ltIndexl] = rightTop[rtIndex] = false;
        }
    }

    void show() {
        for (int row = 0; row < queens.length; row++) {
            for (int col = 0; col < queens.length; col++) {
                if (queens[row] == col) { // 摆放了皇后
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("--------------------------");
    }
}
